#include <stdlib.h>
#include <stdio.h>

namespace STACK {
    
    typedef struct StackNode {
        char data;
        struct StackNode *pNext;
    }STACKNODE, *PSTACKNODE;
    
    typedef struct Stack {
        PSTACKNODE pTop;
        PSTACKNODE pBottom;
    }STACK, *PSTACK;
    
    PSTACK create_stack() {
        PSTACK pS = (PSTACK) malloc(sizeof(STACKNODE));
        pS->pTop = (PSTACKNODE) malloc(sizeof(STACKNODE));
        if(pS==NULL||pS->pTop==NULL) {
            printf("malloc failed\n");
            exit(-1);
        } else {
            pS->pBottom = pS->pTop;
            pS->pBottom->pNext = NULL;
        }
        return pS;
    }
    
    bool is_stack_empty(PSTACK pS) {
        if(pS->pTop==pS->pBottom) {
            return true;
        } else {
            return false;
        }
    }
    
    void push_stack(PSTACK pS, char val) {
        PSTACKNODE pNew = (PSTACKNODE) malloc(sizeof(STACKNODE));
        if(pNew==NULL) {
            printf("malloc failed\n");
            exit(-1);
        } else {
            pNew->data = val;
            pNew->pNext = pS->pTop;
            pS->pTop = pNew;
        }
    }
    
    bool pop_stack(PSTACK pS, char* pData) {
        if(is_stack_empty(pS)) {
            return false;
        } else {
            PSTACKNODE p = pS->pTop;
            *pData = p->data;
            pS->pTop = pS->pTop->pNext;
            free(p);
            p = NULL;
            return true;
        }
    }
    
    void clear_stack(PSTACK pS) {
        if(is_stack_empty(pS)) {
            return ;
        } else {
            PSTACKNODE p = pS->pTop;
            PSTACKNODE r = NULL;
            while(p != pS->pBottom)
            {
                r = p->pNext;
                free(p);
                p = r;
            }
            pS->pTop = pS->pBottom;
        }
    }
    
    void traverse_stack(PSTACK pS) {
        PSTACKNODE pCurrent = pS->pTop;
        while(pCurrent!=pS->pBottom) {
            printf("%c", pCurrent->data);
            pCurrent = pCurrent->pNext;
        }
        printf("\n");
    }
}
